/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */

#ifndef _INSIEME_H_
#define _INSIEME_H_

#include <iostream>
using namespace std;

#define NDEBUG
#include <cassert>

#include "lista/lista.h"



template <class T>
class Insieme {
public:
	Insieme();
	~Insieme();

	//Operatori
	void creaInsieme();
	bool insiemeVuoto();
	bool appartiene(T);
	void inserisci(T);
	void cancella(T);
	Insieme<T> unione(Insieme);
	Insieme<T> intersezione(Insieme);
	Insieme<T> differenza(Insieme);
	int cardinalita();

	//operatori personalizzati
	void print();

private:
	typedef typename Lista<T>::posizione posizione;
	Lista<T> list;
};



/*****************************
 *        DEFINIZIONI        *
 *  dei metodi di Alberobin  *
 *****************************/

template <class T>
Insieme<T>::Insieme() {
	creaInsieme();
}

template <class T>
Insieme<T>::~Insieme() {}

template <class T>
void Insieme<T>::creaInsieme() {}


template <class T>
bool Insieme<T>::insiemeVuoto() {
	return list.listaVuota();
}


template <class T>
bool Insieme<T>::appartiene(T elem) {
	if ( list.listaVuota() )
		return false;
	else {
		posizione pos = list.primoLista();

		while ( !(list.fineLista(pos) ) ) {
			if ( list.leggiLista(pos) == elem )
				return true;
			pos = list.succLista(pos);
		}

		return false;
	} //else
} //appartiene




template <class T>
void Insieme<T>::inserisci(T elem) {
	if (! appartiene(elem)) {
		posizione pos = list.primoLista() ;
		list.insLista(elem, pos);
	}
}



template <class T>
void Insieme<T>::cancella(T elem) {
	if ( list.listaVuota() ) {
		throw "ERRORE";
	} else {
		posizione pos = list.primoLista();
		bool trovato = false;

		while ( (!list.fineLista(pos)) && (!trovato) ) {
			if ( list.leggiLista(pos) == elem ) {
				trovato = true;
				list.cancLista(pos);
			}
			pos = list.succLista(pos);
		} //while
	} //else
}




template <class T>
Insieme<T> Insieme<T>::intersezione(Insieme<T> set) {
	Insieme<T> insiemeIntersezione;

	posizione pos = list.primoLista();

	while ( !list.fineLista(pos) ) {
		T elem = list.leggiLista(pos);
		if ( set.appartiene( elem ) ) {
			insiemeIntersezione.inserisci( elem );
		}
		pos = list.succLista( pos ) ;	
	} //while

	return insiemeIntersezione;
}


template <class T>
Insieme<T> Insieme<T>::unione(Insieme<T> set) {
	Insieme<T> insiemeUnione;

	posizione pos;

	pos = set.list.primoLista();
	while ( !set.list.fineLista(pos) ) {
		insiemeUnione.inserisci( set.list.leggiLista( pos ) );
		pos = set.list.succLista( pos );
	} //while


	pos = list.primoLista();
	while (!list.fineLista(pos)) {
		T elem = list.leggiLista(pos);

		insiemeUnione.inserisci( elem );
		pos = list.succLista(pos) ;
	} //while

	return insiemeUnione;
}




template <class T>
Insieme<T> Insieme<T>::differenza(Insieme<T> set) {
	Insieme<T> differenza;

	posizione pos;
	T elem;
	pos = list.primoLista();
	while (!list.fineLista(pos)) {
		elem = list.leggiLista(pos);
		if ( !set.appartiene(elem) ) 
			differenza.inserisci(elem);
		pos = list.succLista(pos) ;
	} //while	
	return differenza;
}




template <class T>
void Insieme<T>::print() {
	cout << "[ " ;
	posizione pos;
	pos=list.primoLista();
	while (! list.fineLista(pos) ) {
		cout << list.leggiLista(pos) << " ";
		pos = list.succLista(pos) ;
	} //while
	cout << "]" << endl;
}

template <class T>
int Insieme<T>::cardinalita() {
	return list.sizeLista();
}


#endif // _INSIEME_H_
